package 高级班;

public class Problem03_PalindromeMinAdd {

    public static String getPalindrome1(String str) {
        if (str == null || str.length() < 2) {
            return str;
        }
        char[] chas = str.toCharArray();
        int[][] dp = getDP(chas);
        //printMatrix.printMatrix0(dp);
        char[] res = new char[chas.length + dp[0][chas.length - 1]];
        int i = 0;
        int j = chas.length - 1;
        int resl = 0;
        int resr = res.length - 1;
        while (i <= j) {
            if (chas[i] == chas[j]) {
                res[resl++] = chas[i++];
                res[resr--] = chas[j--];
            } else if (dp[i][j - 1] < dp[i + 1][j]) {
                res[resl++] = chas[j];
                res[resr--] = chas[j--];
            } else {
                res[resl++] = chas[i];
                res[resr--] = chas[i++];
            }
        }
        return String.valueOf(res);
    }

    public static int[][] getDP(char[] str) {
        int[][] dp = new int[str.length][str.length];
        for (int j = 1; j < str.length; j++) {
            dp[j - 1][j] = str[j - 1] == str[j] ? 0 : 1;
            for (int i = j - 2; i > -1; i--) {
                if (str[i] == str[j]) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        return dp;
    }

    public static String process_ytx(String s){
        char[] chars = s.toCharArray();
        int[][] dp = getDP(chars);
        //printMatrix.printMatrix0(dp);
        char[] res=new char[chars.length+dp[0][chars.length-1]];
        int i=0;
        int j=s.length()-1;
        int resi=0;
        int resj=res.length-1;
        while (i<=j){
            if (s.charAt(i)==s.charAt(j)){
                res[resi++]=s.charAt(i++);
                res[resj--]=s.charAt(j--);
            }else if (dp[i+1][j]>dp[i][j-1]){
                res[resi++]=s.charAt(j);
                res[resj--]=s.charAt(j--);
            }else{
                res[resi++]=s.charAt(i);
                res[resj--]=s.charAt(i++);
            }
        }
        return String.valueOf(res);
    }
    public static int[][] getDp_ytc(char[] str){
        int[][] dp=new int[str.length][str.length];
        for (int j=1;j< str.length;j++){
            dp[j-1][j]=str[j-1]== str[j]?0:1;
            for (int i=j-2;i>=0;i--){
                if (str[i]==str[j]){
                    dp[i][j]=dp[i+1][j-1];
                }else
                    dp[i][j]=Math.min(dp[i+1][j],dp[i][j-1])+1;
            }
        }
        return dp;
    }

    public static void main(String[] args) {
        String str = "AB1CD2EFG3H43IJK2L1MN";
        System.out.println(getPalindrome1(str));
        System.out.println(process_ytx(str));
    }

}